package arithmetic.sort;

/**
 * Created by jiangfeng on 2017/10/10.
 * 归并排序 优化：
 *
 * todo
 * 和快速排序一样，对于小数组可以使用插入排序或者选择排序，避免递归调用。
 在merge()调用之前，可以判断一下a[mid]是否小于等于a[mid+1]。如果是的话那么就不用归并了，数组已经是有序的。原因很简单，既然两个子数组已经有序了，那么a[mid]是第一个子数组的最大值，a[mid+1]是第二个子数组的最小值。当a[mid]<=a[mid+1]时，数组整体有序。
 为了节省将元素复制到辅助数组作用的时间，可以在递归调用的每个层次交换原始数组与辅助数组的角色。
 在merge()方法中的归并过程需要判断i和j是否已经越界，即某半边已经用尽。可以用另一种方式，去掉检测是否某半边已经用尽的代码。具体步骤是将数组a[]的后半部分以降序的方式复制到aux[]，然后从两端归并。对于数组{1,2,3}和{2,3,5},第一个子数组照常复制，第二个则从后往前复制，最终aux[]中的元素为{1,2,3,5,3,2}。这种方法的缺点是使得归并排序变为不稳定排序。
 */
public class MergeSort2 {

    public static void mergeSort(Integer[] arr) {
        Integer[] temp = new Integer[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        // 复制一个新数组，作为输入数组， 一次性复制提升性能
        System.arraycopy(arr,0,temp,0,arr.length);
        //
        sort(temp, 0, arr.length - 1, arr);
    }

    private static void sort(Integer[] in, int left, int right, Integer[] out) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 这里调换输入和输出的数组可以 节省复制时间
            sort(out, left, mid, in);//左边归并排序，使得左子序列有序
            sort(out, mid + 1, right, in);//右边归并排序，使得右子序列有序
            merge(in, left, mid, right, out);//将两个有序子数组合并操作
        }
    }

    private static void merge(Integer[] in, int left, int mid, int right, Integer[] out) {
        //if(arr[mid]<=arr[mid+1])return;
        int i = left;//临时数组指针
        int j = mid + 1;//右序列指针
        while (left <= mid && j <= right) {
            if (in[left] <= in[j]) {
                out[i++] = in[left++];
            } else {
                out[i++] = in[j++];
            }
        }
        while (left <= mid) {//将左边剩余元素填充进temp中
            out[i++] = in[left++];
        }
        while (j <= right) {//将右序列剩余元素填充进temp中
            out[i++] = in[j++];
        }
    }
}
